package explore.hxx.binarytree.self;

import explore.hxx.binarytree.dependence.TreeNode;

import java.util.*;

/**
 * @author waxijiang
 */
public class AfterOrderTraversal {
    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = null;
        node.right = new TreeNode(2);
        node.right.left = new TreeNode(3);
        node.right.right = null;

        System.out.println(midOrderTraversal(node));

    }

    public static List<Integer> midOrderTraversal(TreeNode root) {
        LinkedList<HashMap<TreeNode, Boolean>> stack = new LinkedList<>();
        // 排除特殊
        if (root != null) {
            stack.push(new HashMap<TreeNode, Boolean>() {{
                put(root, false);
            }});
        }

        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            // 查看栈顶元素
            // 真麻烦
            TreeNode tmpNode = (TreeNode) (stack.getFirst().keySet().toArray()[0]);
            Boolean test = (Boolean) stack.getFirst().values().toArray()[0];
            if (!test) {
                // 标记已经出栈过的元素
                stack.getFirst().put(tmpNode, true);
                // 加入其左右节点
                if (tmpNode.right != null) {
                    stack.push(new HashMap<TreeNode, Boolean>() {{
                        put(tmpNode.right, false);
                    }});
                }
                if (tmpNode.left != null) {
                    stack.push(new HashMap<TreeNode, Boolean>() {{
                        put(tmpNode.left, false);
                    }});
                }
            } else {
                result.add(tmpNode.val);
                stack.pop();
            }


        }
        return result;
    }
}
